package zemberek3.crosscheck;


import zemberek3.structure.TokenSequence;

/**
 * Calculates letter edit distance. Uses a modified and resource low Levenshtein edit distance algorithm.
 */
public class LevenshteinCharDistance extends BaseDistanceCalculator implements DistanceCalculator {

    @Override
    public int sourceSize(TokenSequence sourceSequence) {
        return sourceSequence.asString().length();
    }

    @Override
    public double distance(TokenSequence sourceSequence, TokenSequence targetSequence) {
        checkArguments(sourceSequence, targetSequence);
        String targetString = targetSequence.asString();
        String sourceString = sourceSequence.asString();
        int n;
        double p[]; //'previous' cost array, horizontally
        double d[]; // cost array, horizontally
        double _d[]; //placeholder to assist in swapping p and d

        n = sourceString.length();
        p = new double[n + 1];
        d = new double[n + 1];

        final int m = targetString.length();
        if (n == 0 || m == 0) {
            return Math.abs(n - m);
        }

        // indexes into strings s and t
        int i; // iterates through s
        int j; // iterates through t

        char t_j; // jth char

        double cost; // cost

        for (i = 0; i <= n; i++) {
            p[i] = i;
        }

        for (j = 1; j <= m; j++) {
            t_j = targetString.charAt(j - 1);
            d[0] = j;

            for (i = 1; i <= n; i++) {
                cost = sourceString.charAt(i - 1) == t_j ? 0 : 1;
                // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
                d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
            }

            // copy current distance counts to 'previous row' distance counts
            _d = p;
            p = d;
            d = _d;
        }

        // our last action in the above loop was to switch d and p, so p now
        // actually has the most recent cost counts
        return p[n];

    }
}
